package org.algorithm.熊猫.回溯算法;

import java.util.HashMap;

/**
 * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/
 */
public class $5月1日$划分为k个相等的子集 {


    public boolean canPartitionKSubsets(int[] nums, int k) {
        //当k数量大于元素数量时，完全不够分
        if (k > nums.length) return false;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //当总和不能整除k时，无论如何分每个子集和不能相等
        if (sum % k != 0) return false;

        int used = 0;
        int target = sum / k;
        return backtrack(k, 0, nums, 0, used, target);
    }

    HashMap<Integer, Boolean> memo = new HashMap<>();


    /**
     *
     * @param k  剩余桶的数量
     * @param bucket 当前桶累加和
     * @param nums   原始数组
     * @param start  起始索引位置
     * @param used   标记变量，二进制存储了当前索引位置数字是否被使用
     * @param target
     * @return
     */
    private boolean backtrack(int k, int bucket, int[] nums, int start, int used, int target) {
        if (k == 0) {
            // 所有桶都被装满了，⽽且 nums ⼀定全部⽤完了
            return true;
        }
        if (bucket == target) {
            // 装满了当前桶，递归穷举下⼀个桶的选择
            // 让下⼀个桶从 nums[0] 开始选数字
            boolean res = backtrack(k - 1, 0, nums, 0, used, target);
            // 缓存结果
            memo.put(used, res);
            return res;
        }

        if (memo.containsKey(used)) {
            // 避免冗余计算
            return memo.get(used);
        }


        for (int i = start; i < nums.length; i++) {
            // 剪枝
            if (((used >> i) & 1) == 1) { // 判断第 i 位是否是 1
                // nums[i] 已经被装⼊别的桶中
                continue;
            }
            if (nums[i] + bucket > target) {
                continue;
            }
            // 做选择
            used |= 1 << i; // 将第 i 位置为 1
            bucket += nums[i];
            // 递归穷举下⼀个数字是否装⼊当前桶
            if (backtrack(k, bucket, nums, i + 1, used, target)) {
                return true;
            }
            // 撤销选择
            used ^= 1 << i; // 将第 i 位置为 0
            bucket -= nums[i];
        }
        return false;
    }
}
